package com.heima.leetcode.practice;

import java.util.Arrays;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 416. 分割等和子集
 * @date 2025/2/24 10:05
 */
public class E416 {

    /**
     * <h3>方法一：滑动窗口法（不能处理所有情况，当需要减的数在当前减数后面的时候不行）</h3>
     *
     * @param nums 数组
     * @return 是否可以分割成两个和相等的子集
     */
    public boolean canPartition1(int[] nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        // 如果总和是奇数，则无法分割成两个和相等的子集
        if ((total & 1) == 1) {
            return false;
        }
        int target = total >> 1; // 目标值为总和的一半
        Arrays.sort(nums);
        total = 0;
        int left = 0, right = 0;
        // nums = {14, 9, 8, 4, 3, 2}的时候不行，target = 20，9 + 8 = 4 +3 + 2 = 26，
        // 说明要减的是2和4但是局限是只能小的一个一个减
        while (right < nums.length) {
            total += nums[right++];
            while (total > target) {
                total -= nums[left++];
            }
            if (total == target) return true;
        }
        return false;
    }

    /**
     * <h3>方法二：回溯，会超出时间限制</h3>
     *
     * @param nums 数组
     * @return 是否可以分割成两个和相等的子集
     */
    public boolean canPartition2(int[] nums) {
        int total = 0;
        for (int num : nums) {
            total += num;
        }
        // 如果总和是奇数，则无法分割成两个和相等的子集
        if ((total & 1) == 1) {
            return false;
        }
        int target = total >> 1; // 目标值为总和的一半
        Arrays.sort(nums);
        return dfs1(nums, target, 0);
    }

    /**
     * 回溯法
     *
     * @param nums   数组
     * @param target 目标值
     * @param start  开始位置
     * @return 是否可以分割成两个和相等的子集
     */
    private boolean dfs1(int[] nums, int target, int start) {
        if (start == nums.length) return false;
        target -= nums[start];
        if (target == 0) return true;
        if (target < 0) return false;
        for (int i = start; i < nums.length; i++) {
            if (dfs1(nums, target, i + 1)) {
                return true;
            }
        }
        return false;
    }

    /**
     * <h3>方法三：动态规划</h3>
     *
     * @param nums 数组
     * @return 是否可以分割成两个和相等的子集
     */
    public boolean canPartition3(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;
        // 如果总和是奇数，则无法分割成两个和相等的子集
        if ((total & 1) == 1) return false;
        int target = total >> 1; // 目标值为总和的一半
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // 和为0的子集总是存在的（即空集）
        // 动态规划填充dp数组
        for (int num : nums)
            for (int i = target; i >= num; i--)
                dp[i] = dp[i] || dp[i - num];
        return dp[target];
    }


    public static void main(String[] args) {
        int[] nums = {14, 9, 8, 4, 3, 2};
        System.out.println(new E416().canPartition1(nums));
    }
}
